1. Field of the Invention
The present application relates generally to an improved data processing apparatus and method. More specifically, the present application relates to mechanisms for performing parallel intrusion search operations in a hierarchical VLSI design using a substituting scan line.
2. Background of the Invention
A hierarchical Very Large Scale Integration (VLSI) integrated circuit design D consists of cells which contain instances of other cells and geometric objects. Geometric objects are polygons, lines, and points. An instance is the placement of the content of a cell C into the coordinate system of a cell P through a coordinate transform.
FIGS. 1A-1D provide a simple example of a hierarchical design representation. A cell A contains two instances B1 102 and B2 104 of a cell B and one rectangle 110 on a first layer, referred to as layer Blue. A cell B contains two instances 112 and 114 of cell C, which contains three rectangles 120-140 on layer Blue and three rectangles 150-170 on a second layer, referred to as layer Red. Thus, cell B may be expressed as a combination of instances of cell C and cell A may be expressed as a combination of instances of cell B.
As shown in FIG. 1D, for each hierarchical VLSI design D there exists an equivalent flat VLSI design Df. A geometric object in Df has a one-to-one correspondence with an instance path in D. An instance path I representing a flat geometric object consists of a cell in D followed by a number of instances (there may be zero) and terminated by a reference to a geometric object in the lowest cell in the path. For example, an instance path in the example of FIG. 1D may be consist of cell node A, edge B2, cell node B, edge C2, and cell node C. Note that an instance path I that starts in a cell P that is not the top cell of design D expresses an entire set of instances. The set contains one element for each flat instance of cell P in design D. FIGS. 2A-2C illustrate a corresponding representation of each cell in a flattened form.
Analogously, there is a correspondence between an interaction between two geometric objects in Df and the two corresponding instance paths in D. Such an interaction is defined by two instance paths that start in the same cell P and optional interaction properties. If cell P is not the top cell, such an interaction represents an entire set of interactions, again one for each instance of cell P. Consequently, an interaction instance is defined by a tupelo consisting of a cell Q, a sequence of instance, and a reference to the interaction in the lowest cell P of the path.
An “intrusion” is an interaction, e.g., an overlap, between two or more geometric objects within a hierarchical VLSI design D. An interaction of limited distance expressed in a cell P that is not the top cell of D is also called a “nested intrusion.” An interaction in Df, which corresponds to an interaction instance whose path starts in the top cell of D, is called a “flat intrusion.” There exists an intrusion I(d) between two geometric objects A and B in D if the minimum distance between the point sets, i.e. the collection of shapes, dots, lines, curves, etc., of geometric objects A and B, represented by the two instance paths, is equal to or less than a distance d in a specified metric M, typically the L∞ metric. The minimum distance between two point sets (e.g., two rectangles) in Euclidian metric is the length of the shortest line that exists which ‘touches’ both point sets, e.g., if the minimum distance d=0, then the shapes have to touch each other.
Intrusion searching in a hierarchical design D is the process of finding all intrusions for a given distance d for a specified subset of the geometric objects in a hierarchical VLSI design D in the most nested representation. The typical methodology to specify subsets of geometric objects in the design D that are of interest is through the specification of layers of the VLSI design, e.g., finding interactions between geometric shapes on one metal layer or another.